Field of the Invention
This invention relates to systems and methods for storing and accessing data in a flash memory system.
Background of the Invention
Typically flash memory includes many data blocks (a smallest erasable unit). Each data block includes several data pages (a smallest programmable unit). Read and write operations may be performed at page level. Erase operations are only performed at block level. Due to internal characteristic of flash memory, a flash page cannot be overwritten. It needs to be erased prior to program operation. Because erase operation is very time intensive (it is a block level operation) and also reduces the flash block lifetime (each flash block is associated with fixed number of erase cycle), flash vendors often perform flash page overwrite operation as 1) write a new flash page, 2) invalidate an old flash page.
This leads to many versions of same page, all these versions except the recent version of the page is invalid once the data is modified. Several invalid copies of the same page will increase device space consumption, which leads to increase in write amplification (WA).
Blocks with many invalid pages are still not suitable for reuse because valid pages cannot be erased. Device garbage collection (GC) is responsible for reclaiming the invalid pages by moving the valid pages into a new block, once the block is free of all valid pages, it is erased, and this block now can be used by incoming writes.
Device GC does not run very frequently, because the GC process will interfere with the device throughput. Out of many blocks, which have many invalid pages, only certain blocks (victim blocks) are picked by the Garbage Collection process for cleanup. Identifying victim blocks is usually done if the block has maximum number of invalid pages. Because of all these thresholds and limitations, the actual amount of physical information written is a multiple of the logical amount intended to be written. Therefore write implication caused by Device GC=(Data written to Flash/Actual Data written by host)
Certain object storing applications, such as level DB and rocks DB, are designed as log-structured merge-tree (LSM) systems. Similar to SSDs (solid state drive), these applications have many invalid versions of objects that are no longer required. A process called compaction is run often, which will compact the database by removing invalid versions of objects. These applications running on SSDs will likewise create write amplification by storing invalid objects. The WA caused by the database is (Data written to Flash/Actual data written to database). The total WA of system is therefore WA of the flash drive times the WA of the database.
The apparatus and methods disclosed herein provide an improved approach for avoiding write amplification in flash storage systems.